import java.util.Arrays;

/**
 * @author LKQ
 * @date 2021/12/20 21:19
 * @description 我是一点不会，官方解法一、排序加二分，想到了二分但是不知道咋弄。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] houses = {1, 5, 10}, heaters = {7, 3};
        System.out.println(solution.findRadius(houses, heaters));
    }

    public int findRadius(int[] houses, int[] heaters) {
        int ans = 0;
        Arrays.sort(heaters);
        for (int house : houses) {
            // 房屋最近的一个供暖器位置
            int i = binarySearch(heaters, house);
            // 下一个加热器位置
            int j = i + 1;
            // 房屋据最近供暖期距离，i < 0即为-1时，说明该房屋在所有供暖器的左边，距离设置为Max
            int leftDistance = i < 0 ? Integer.MAX_VALUE : house - heaters[i];
            // i = -1时，j = 0, 以房屋为中心，右边距离为最近的供暖器位置减去房屋位置。
            int rightDistance = j >= heaters.length ? Integer.MAX_VALUE : heaters[j] - house;
            // 房屋左右距离取最小值，即为供暖器对该房屋的最小距离
            int curDistance = Math.min(leftDistance, rightDistance);
            // 对所有房屋的最小距离取最大值，即为满足所有房屋取暖的最小半径。
            ans = Math.max(ans, curDistance);
        }
        return ans;

    }

    /**
     * 二分查找，返回目标值在数组中的位置
     * @param nums 排序后数组
     * @param target 目标值
     * @return 目标值位置
     */
    public int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        if (nums[left] > target) {
            // 最小的都比目标值大，返回-1
            return -1;
        }
        while (left < right) {
            int mid = (right - left + 1) / 2 + left;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
}
